Backtracking：通常是用在需要紀錄路徑的 DFS 時。

1. 往前搜尋，發現目前的元素不符合條件，就退回去上一步，並恢復原狀，再去做別的嘗試。
2. 當紀錄的路徑是想要的結果時（例如 DFS 深度），記錄下來，退回上一步。

常見的 itertools 中會用到的 combination, permutation 還有 subset 的實作。
都可以試試看用 backtracking 做，當然也可以用 DP。
77. Combinations
46. Permutations
78. Subsets

對於一般新手來說，一開始可能比較難理解這部分的遞迴，或是容易把不同的解法搞混。

常見錯誤：append 還是 +=

在寫 subsets 時，我一開始不太會構建我的遞迴，
雖然知道要有 base case，要有遞迴的部分，和 return，但常常還是寫得亂七八糟。
尤其是對於陣列的元素到底要 append 還是用 +=？現在拿到的 list 有可能為空嗎？等等
要仔細想清楚。
這個錯誤其實也不是特別針對 backtracking，而是要紀錄狀態或元素時可能會不小心搞錯的。

以 subsets 這類型題目為例：

1. 如果是呼叫了原來的 function，return 的型態就很確定，一定是 2d array
   例如這樣：

 def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]
        l = self.subsets(nums[:-1])
        ans = [term + [nums[-1]] for term in l] + l
        return ans

2. 如果是 dp，要基於一個變數去增加的話
   這個 ans 也是個 2d array，取出來的 e 則是一個 list。
   e.append(nums[i]) 會回傳 None，所以只能用 +

ans = []
for i in range(len(nums)):
    ans += ([[nums[i]]] + [[nums[i]] + e for e in ans])

3. 或是用 backtracking 產生各種長度的 combination
   因為 cur 是一個 list，所以 append 之後傳已經加完新元素的 cur 進去遞迴中。

def backtrack(first = 0, cur):
    if len(cur) == k:  # 到達深度 k
        output.append(cur[:])
        return
    for i in range(first, n):
        cur.append(nums[i]) 
        backtrack(i + 1, cur)
        cur.pop() # 恢復狀態再去加下一個數字

4. 還有各種其他寫法
   我每次寫都寫出不一樣的、奇形怪狀的東西ＸＤ
   所以主要還是要練習能夠快速判斷自己在幹嘛，並注意 append 不會回傳東西，+ 可以直接得到合併好的陣列。

對於 backtracking，
只要知道自己在幹嘛，順著思路，
自然而然在某個地方就是需要做狀態的恢復，
才能去試試下一條路。
因為關心的不只是最後找到的元素，而是整條 dfs 的路線。
對於 combinations 來說，這條路線就是其中一個合法的 combination，只要找到用完全部元素的那條（也就是到達最深的深度）就紀錄、return、恢復前一動。
對於 matrix 中找單字（昨天提的 word search） 來說，這條路線就是目前找到的 substring，只要發現下一步找到的元素不能組成 target，就恢復上一動；如果找到了，就回傳 true